Beginning in the early 1970s, the Automated Intercept System (AIS) was installed in some Bell System telephone offices to provide automated announcements to callers who had reached out-of-service or changed telephone numbers. This service was and is supported by a data base system called the File Administration System (FAS). The FAS is a minicomputer processing system and contains customer files which store customer information such as new telephone numbers or information geared to cause automatic interception of calls to certain customers. The stored customer information is accessible by using customer telephone numbers as an input search parameter.
In 1976 the Bell System introduced the Common Channel Interoffice Signaling System (CCIS) into the Bell network. CCIS is a packet data switching and transmission system which is overlaid onto the telephone network and provides signaling capability for the establishment of telephone calls. CCIS is described in 57 Bell System Technical Journal, No. 2, at page 230 et seq. CCIS, in conjunction with the stored program controlled network which is evolving in the Bell System, has the capability to offer a multitude of new, enhanced and sophisticated telephone services. Some examples are Auto Bill Calling, new "800" number type services, and Person Locator services. Auto Bill Calling with replace collect, credit card, and third number billing station-to-station calling. This service is described in U.S. Pat. No. 4,162,377 which issued to A. B. Mearns on July 24, 1979. New "800" service is described in U.S. Pat. No. 4,191,860 which issued to R. B. Weber on Mar. 4, 1980. Person Locator service is described in U.S. patent application Ser. No. 113,383, filed by D. S. Jordon et al on Jan. 18, 1980.
The provision of these new services requires the use of a data management system by telephone companies to store massive amounts of customer information. Ultimately, information would be stored for each customer of a given telephone company. This translates to magnitudes in the order of 500 million bytes of information for one data management system. It is anticipated that large numbers of accesses to the customer information will be required to obtain or to change the stored information. For reasons of economy, it is desirable to use a minicomputer processing system such as the system referred to earlier, while still providing massive storage and access capacity. To accomplish these objectives, a need exists to improve the known data management system data structures and search techniques.
One known search method is briefly described by Per-Ake Larson in an article "Dynamic Hashing" in Bit, Volume 18, 1978, pp. 184-201. To reduce the number of disc accesses required to locate any data record, thereby to improve efficiency and data throughput, a single binary bit string is used to define the location of stored information relating to an input search parameter. The ones and zeros of the bit string define the path through a hierarchical tree to locate the stored data. Unfortunately, however, this techique results in a bit string that is so large for a reasonably large data management system that excessive main storage is required to store the string. Moreover, even if the string is maintained in secondary memory, such as disc memory, the length of the string still determines the size of required main memory when the string is read. Otherwise, the string must be read piecemeal, which increases the required number of disc accesses.